package com.czk.search;

import java.util.Arrays;

/**
 * 斐波那契查找算法
 * 有点难懂，需要结合博客来帮助理解
 * @Author:ChenZhangKun
 * @Date: 2020/7/2 20:02
 */
public class FibonacciSearch {
    public static int maxSize=20;
    public static void main(String[] args) {
        int[] array={1,2,3,4,5,6};
        System.out.println(fibonacciSearch(array, 6));
    }
    // 后面需要low+f[k-1]-1,需要使用斐波那契数列，首先要获到一个斐波那契数列
    public static int[] fib(){
        int[] f=new int[maxSize];
        f[1]=1;
        f[0]=1;
        for (int i = 2; i <maxSize ; i++) {
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }
    public static int fibonacciSearch(int[] a,int key){
        int left=0;
        int right=a.length-1;
        int k=0;
        int mid=0;
        // 拿到斐波那契数列
        int[] fib = fib();
        // 拿到斐波那契分割的下标
        while (key>fib[k]-1){
            k++;
        }
        // 因为f[k]的值可能大于数组的长度，因此需要使用Arrays类来构造新数组指向a
        int[] temp= Arrays.copyOf(a,fib[k]);
        // 把新构建的数组大于原素组的元素用a[k]填充
        for (int i = right+1; i <temp.length ; i++) {
            temp[i]=a[right];
        }
        // while循环处理，找到我们的key
        while (left<=right){
            mid=left+fib[k-1]-1;
            if (key<temp[mid]){
                // 向左边查找
                right=mid-1;
                k--;
            }else if (key>temp[mid]){
                // 向右边查找
                left=mid+1;
                k-=2;
            }else {
                if (mid<=right){
                    return mid;
                }else {
                    return right;
                }
            }
        }
        return -1;
    }
}
